﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LeetCodeSolutions
{
    /// <summary>
    /// LeetCode题库20 有效的括号
    /// </summary>
    class LeetCode20: LeetCodeBase
    {
        public override void Execute()
        {
            CommonFuntions.Print(IsValid("){"));
        }

        public bool IsValid(string s)
        {
            if (string.IsNullOrEmpty(s))
            {
                return false;
            }

            int length = s.Length;
            if (length % 2 == 1)//奇数括号对
            {
                return false;
            }

            for (int i = 0; i < length; i++)
            {
                bracketsList.Add(new Bracket(s[i].ToString()));
            }

            Stack<Bracket> bracketsStack = new Stack<Bracket>();
            bool isMatch = true;

            int index = 0;
            while (bracketsStack.Count > 0 || index < length - 1)
            {
                if(index >= length)
                {
                    break;
                }

                CommonFuntions.Print("index " + index);
                Bracket bracket = bracketsList[index];
                if (bracket.isOther)
                {
                    //index++;
                    continue;
                }

                if (bracket.isLeft)
                {
                    bracketsStack.Push(bracket);
                    CommonFuntions.Print("Push " + bracket.value);
                }
                else if (!bracket.isLeft)
                {
                    if (bracketsStack.Count > 0)
                    {
                        Bracket popBracket = bracketsStack.Pop();
                        CommonFuntions.Print("Pop " + popBracket.value);
                        if (!IsMatch(popBracket, bracket))
                        {
                            CommonFuntions.Print("Compare " + bracket.value + " " + popBracket.value);
                            isMatch = false;
                        }
                    }
                    else
                    {
                        isMatch = false;
                    }
                }

                index++;
            }

            if (bracketsStack.Count != 0)
            {
                return false;
            }

            if (!isMatch)
            {
                return false;
            }

            CommonFuntions.Print("##Final");
            return true;
        }

        public List<Bracket> bracketsList = new List<Bracket>();

        public bool IsMatch(Bracket bracket1, Bracket bracket2)
        {
            if (bracket1.isLeft == bracket2.isLeft)
            {
                return false;
            }

            switch (bracket1.value)
            {
                case "{":
                    if (bracket2.value == "}")
                    {
                        return true;
                    }
                    break;
                case "[":
                    if (bracket2.value == "]")
                    {
                        return true;
                    }
                    break;
                case "(":
                    if (bracket2.value == ")")
                    {
                        return true;
                    }
                    break;
            }

            return false;
        }

        public class Bracket
        {
            public string value;
            public bool isLeft;
            public bool isOther = false;

            public Bracket(string _value)
            {
                value = _value;
                if (value == "{" || value == "[" || value == "(")
                {
                    isLeft = true;
                }
                else if (value == "}" || value == "]" || value == ")")
                {
                    isLeft = false;
                }
                else
                {
                    isOther = true;
                }
            }
        }
    }
}